package com.sgg.datastructure.circleLinkedList;

public class CircleLinkedList {
    private Boy first = new Boy(0);

    public CircleLinkedList() {
    }

    public void add(int num) {
        if (num < 2) {
            System.out.println("数量必须大于等于2");
            return;
        }
        Boy temp = null;
        for (int i = 1; i <= num; i++) {
            if (i == 1) {
                first = new Boy(1);
                temp = first;
                first.setNext(first);
            } else {
                Boy boy = new Boy(i);
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }
        }
    }

    /**
     * 不断遍历,如果指针下一个是头结点,打印下就退出
     */
    public void show() {
        Boy temp = first;

        while (true) {
            System.out.println(temp.getNo());
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();

        }
    }

    public int size() {
        int size = 1;
        Boy temp = first;
        while (temp.getNext() != first) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }


    /**
     * 描述:n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列
     * 出圈的思路
     * 1.创建个辅助指针,指向队列的最后一个位置(已经有了1个指向第一个位置的)
     * 2.辅助指针和头指针先向前移动k-1个位置
     * 3.辅助指针和头指针向前移动m-1个位置
     * 4.出列的做法:头指针移动下一个位置,辅助指针指向新头指针位置
     * 5.最终尾指针和头指针指向同一个位置,结束
     */
    public int finalPerson(int k, int m) {
        if (k > size()) {
            throw new RuntimeException("k必须小于小朋友的总数");
        }
        if (m < 1) {
            throw new RuntimeException("m必须大于2");
        }
        Boy temp = first;
        while (true) {
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
        //5
        while (temp != first) {
            //2
            for (int i = 0; i < k - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            //3
            for (int i = 0; i < m - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            System.out.printf("小朋友%d出列\n", first.getNo());
            //4
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.println("final winner:"+first.getNo());
        return first.getNo();
    }


    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        int n = 5;
        int k =1;
        int m = 2;
        circleLinkedList.add(n);
        circleLinkedList.show();
        System.out.println("size:" + circleLinkedList.size());
        int result1 = circleLinkedList.finalPerson(k, m);
    }
}
